package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class Solution_373 {

    public static void main(String[] args) {
        Solution_373 model = new Solution_373();
//        System.out.println(model.kSmallestPairs(new int[]{1,7,11}, new int[]{2,4,6}, 3));
//        System.out.println(model.kSmallestPairs(new int[]{1,1,2}, new int[]{1,2,3}, 2));
        System.out.println(model.kSmallestPairs(new int[]{1,1,2}, new int[]{1,2,3}, 10));
//        System.out.println(model.kSmallestPairs(new int[]{1,2}, new int[]{3}, 3));
//        System.out.println(model.kSmallestPairs(new int[]{1,2,4,5,6}, new int[]{3,5,7,9}, 20));
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        List<List<Integer>> list = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]);
        queue.add(new int[]{0, 0});
        if (nums1.length > 1) {
            queue.add(new int[]{1, 0});
        }
        while (k-->0 && !queue.isEmpty()) {
            int[] poll = queue.poll();
            List<Integer> temp = new ArrayList<>();
            temp.add(nums1[poll[0]]);
            temp.add(nums2[poll[1]]);
            list.add(temp);
            if (poll[1] + 1 < nums2.length) {
                queue.add(new int[]{poll[0], poll[1] + 1});
//                Set<Integer> set = map.computeIfAbsent(poll[0], e -> new HashSet<>());
//                if (!set.contains(poll[1] + 1)) {
//                    queue.add(new int[]{poll[0], poll[1] + 1});
//                    set.add(poll[1] + 1);
//                }
            }
//            if (poll[0] + 1 < nums1.length) {
//                Set<Integer> set = map.computeIfAbsent(poll[0] + 1, e -> new HashSet<>());
//                if (!set.contains(poll[1])) {
//                    queue.add(new int[]{poll[0] + 1, poll[1]});
//                    set.add(poll[1]);
//                }
//            }
        }
        return list;
    }
}
